<html>
  <head>
    <meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>RocksDB Write Amplification Optimazation | Elvis Zhang</title>
<meta name="description" content="The easy way or the right way." />
<link rel="shortcut icon" href="https://blog.shunzi.tech/favicon.ico">
<link rel="stylesheet" href="https://blog.shunzi.tech/styles/main.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css">

<script data-ad-client="ca-pub-7661668224317940" async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<script src="https://blog.shunzi.tech/media/js/jquery.min.js"></script>
<script src="https://blog.shunzi.tech/media/js/masonry.pkgd.min.js"></script>
<script src="https://blog.shunzi.tech/media/js/aos.js"></script>
<script src="https://blog.shunzi.tech/media/js/pace.min.js"></script>
<script src="https://blog.shunzi.tech/media/js/view-image.min.js"></script>
<script src="https://blog.shunzi.tech/media/js/jquery.magnific-popup.min.js"></script>
<script src="https://blog.shunzi.tech/media/js/functions.js"></script>
    <meta name="referrer" content="never">
    <meta name="description" content="

The write amplification is severe in RocksDB and results in significant performance degradation. And we will summarize..." />
    <meta name="keywords" content="KVS,存储" />
    <script src="https://blog.shunzi.tech/media/js/waterfall.min.js"></script>
    <script src="https://blog.shunzi.tech/media/js/prism.min.js"></script>
  </head>
  <body>
            <header id="header" class="grid-container">
        <!-- start: .menu-wrapper -->
        <div class="menu-mobile"> 
          <i class="fa fa-reorder"></i>
        </div>
        <div class="menu-wrapper">
          <div class="">
            <div class="logo">
              <a href="https://blog.shunzi.tech"><img src="\media\images\custom-headerLogo.jpg" alt=""></a>
            </div>
            <!-- start: .main-nav -->

            <nav class="main-nav grid-container grid-parent">
              <ul id="menu-header" class="menu gradient-effect">
                <li class=""><a href="https://blog.shunzi.tech" class="menu">首页</a></li>
                
                  <li class="" >
                    <a href="/archives" class="menu">
                      归档
                    </a>
                  </li>
                
                  <li class="" >
                    <a href="/tag/diary" class="menu">
                      随笔
                    </a>
                  </li>
                
                  <li class="" >
                    <a href="/movies" class="menu">
                      观影
                    </a>
                  </li>
                
                  <li class="" >
                    <a href="/post/about" class="menu">
                      关于
                    </a>
                  </li>
                
                <li class="search-menu-item hide-on-mobile hide-on-tablet"><a href="#search-lightbox" class="lightbox mfp-inline"><i class="fa fa-search-line"></i></a></li>
              </ul>
            </nav>
            <a href="#search-lightbox" class="lightbox epcl-search-button mfp-inline hide-on-tablet hide-on-desktop"><i class="fa fa-search-line"></i></a>
            <!-- end: .main-nav -->
            <div class="clear"></div>
            <div class="border hide-on-tablet hide-on-mobile"></div>
          </div>    
          <div class="clear"></div>
        </div>
        <!-- end: .menu-wrapper -->
        <div class="clear"></div>
      </header>
      <div class="hide-on-mobile hide-on-tablet hide-on-desktop">
        <div id="search-lightbox" class="grid-container grid-small grid-parent mfp-hide">
          <div class="search-wrapper section">
            <form id="gridea-search-form" data-update="1610809361880" action="/search/index.html" class="search-form" _lpchecked="1">
              <input type="text" name="q" id="s" value="" class="search-field" placeholder="搜点啥..." aria-label="搜点啥..." required="">
              <button type="submit" class="submit" aria-label="Submit">
                <i class="fa fa-search-line"></i>
              </button>
            </form>
          </div>
        </div>
      </div>

      <main id="single" class="main grid-container fullcover no-sidebar aos-init aos-animate" data-aos="fade">

        <div class="center content">
          <div class="featured-image cover" style="background-image: url('https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210112165715.png');">
            <div class="meta top"> 
              <time class="meta-info" style="float:left;" datetime="2020-12-10"><i class="fa fa-calendar"></i><span class="lately">1 个月前</span></time>
              
              <a href="https://blog.shunzi.tech/post/RocksDB-Write-Amp/#comments" class="comments meta-info" title="">
                <i class="fa fa-comment remixicon"></i><span class="comment-count valine-comment-count" data-xid="/RocksDB-Write-Amp/"> </span>
              </a>
              <span id="/RocksDB-Write-Amp/" class="leancloud_visitors views-counter meta-info" title=""><i class="fa fa-leancloud remixicon"></i><span class="leancloud-visitors-count"></span></span>
              
            </div>
            <div class="info">
              <div class="tags ">
                
                      <a href="https://blog.shunzi.tech/tag/l8sKsLUAi/" class="ctag ctag-0 ctag-l8sKsLUAi" aria-label="">KVS</a>
                    
                      <a href="https://blog.shunzi.tech/tag/3zCwFWPHxH/" class="ctag ctag-1 ctag-3zCwFWPHxH" aria-label="">存储</a>
                    
              </div>
              <h1 class="title ularge white bold">RocksDB Write Amplification Optimazation</h1>
            </div>
          </div>
        </div>  

        <div class="epcl-page-wrapper">
          <div class="left-content grid-70 np-mobile">
            <article class="main-article post">
              <section class="post-content">
                <div class="text">
                  <blockquote>
<ul>
<li>The write amplification is severe in RocksDB and results in significant performance degradation. And we will summarize the main reasons for write amplification.</li>
<li>A lot of researchers dedicate to reduce write amplification whether in academia or industry. And we will summarize the solutions and try to classfify solutions.</li>
</ul>
</blockquote>
<!-- more -->
<h1 id="introduction">Introduction</h1>
<h2 id="rocksdb">RocksDB</h2>
<h3 id="references">References</h3>
<ul>
<li>official site: https://rocksdb.org/</li>
<li>doc: https://github.com/facebook/rocksdb/wiki</li>
<li>src: https://github.com/facebook/rocksdb/</li>
</ul>
<h3 id="brief-intro">Brief Intro</h3>
<ul>
<li>RocksDB is a storage engine with key/value interface, where keys and values are arbitrary byte streams. It is a C++ library. It was developed at Facebook based on LevelDB and provides backwards-compatible support for LevelDB APIs.
<ul>
<li>RocskDB Features that are not in LevelDB: https://github.com/facebook/rocksdb/wiki/Features-Not-in-LevelDB</li>
</ul>
</li>
</ul>
<h3 id="architecture">Architecture</h3>
<figure data-type="image" tabindex="1"><img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20201228165114.png" alt="20201228165114" loading="lazy"></figure>
<h4 id="components">Components</h4>
<h5 id="memtable">MemTable</h5>
<ul>
<li>
<p><strong>MemTable</strong> is an in-memory data-structure holding data before they are flushed to SST files. It serves both read and write - new writes always insert data to memtable, and reads has to query memtable before reading from SST files, because data in memtable is newer. Once a memtable is full, it becomes immutable and replace by a new memtable. A background thread will flush the content of the memtable into a SST file, after which the memtable can be destroyed.</p>
<ul>
<li><strong>Skiplist MemTable</strong>: Skiplist-based memtable provides general good performance to both read and write, random access and sequential scan. Besides, it provides some other useful features that other memtable implementations don't currently support, like Concurrent Insert and Insert with Hint.
<blockquote>
<ul>
<li><strong>InsertWithHint</strong>: Inserts a key allocated by AllocateKey with a hint of last insert position in the skip-list. If hint points to nullptr, a new hint will be populated, which can be used in subsequent calls. Friendly for sequential inserts</li>
</ul>
</blockquote>
</li>
<li><strong>HashSkiplist MemTable</strong>: As their names imply, HashSkipList organizes data in a hash table with each hash bucket to be a skip list, while HashLinkList organizes data in a hash table with each hash bucket as a sorted single linked list. Both types are built to reduce number of comparisons when doing queries. One good use case is to combine them with PlainTable SST format and store data in RAMFS.</li>
</ul>
</li>
<li>
<p><strong>Mutable/Immutable</strong>: When mutable memtable is full, the memtable becomes immutable and can not be moddfied.</p>
</li>
<li>
<p><strong>Flush</strong>: <strong>MemTable -&gt; SSTable</strong></p>
<ol>
<li>
<p>Memtable size exceeds <code>write_buffer_size</code> after a write.</p>
<ul>
<li><code>write_buffer_size</code>: Size of a single memtable.</li>
</ul>
</li>
<li>
<p>Total memtable size across all column families exceeds <code>db_write_buffer_size</code>, or <code>write_buffer_manager</code> signals a flush. In this scenario the largest memtable will be flushed.</p>
<ul>
<li><code>db_write_buffer_size</code>: Total size of memtables across column families. This can be used to manage the total memory used by memtables.</li>
<li><code>write_buffer_manager</code>: Instead of specifying a total size of memtables, user can provide their own write buffer manager to control the overall memtable memory usage. Overrides <code>db_write_buffer_size</code>.</li>
</ul>
</li>
<li>
<p>Total WAL file size exceeds <code>max_total_wal_size</code>. In this scenario the memtable with the oldest data will be flushed, in order to allow the WAL file with data from this memtable to be purged.</p>
</li>
</ol>
</li>
<li>
<p><strong>Comparison</strong></p>
</li>
</ul>
<table>
<thead>
<tr>
<th>Mem Table Type</th>
<th>SkipList</th>
<th>HashSkipList</th>
<th>HashLinkList</th>
<th>Vector</th>
</tr>
</thead>
<tbody>
<tr>
<td>Optimized Use Case</td>
<td>General</td>
<td>Range query within a specific key prefix</td>
<td>Range query within a specific key prefix and there are only a small number of rows for each prefix</td>
<td>Random write heavy workload</td>
</tr>
<tr>
<td>Index type</td>
<td>binary search</td>
<td>hash + binary search</td>
<td>hash + linear search</td>
<td>linear search</td>
</tr>
<tr>
<td>Support totally ordered full db scan?</td>
<td>naturally</td>
<td>very costly (copy and sort to create a temporary totally-ordered view)</td>
<td>very costly (copy and sort to create a temporary totally-ordered view)</td>
<td>very costly (copy and sort to create a temporary totally-ordered view)</td>
</tr>
<tr>
<td>Memory Overhead</td>
<td>Average (multiple pointers per entry)</td>
<td>High (Hash Buckets + Skip List Metadata for non-empty buckets + multiple pointers per entry)</td>
<td>Lower (Hash buckets + pointer per entry)</td>
<td>Low (pre-allocated space at the end of vector)</td>
</tr>
<tr>
<td>MemTable Flush</td>
<td>Fast with constant extra memory</td>
<td>Slow with high temporary memory usage</td>
<td>Slow with high temporary memory usage</td>
<td>Slow with constant extra memory</td>
</tr>
<tr>
<td>Concurrent Insert</td>
<td>Support</td>
<td>Not support</td>
<td>Not support</td>
<td>Not support</td>
</tr>
<tr>
<td>Insert with Hint</td>
<td>Support (in case there are no concurrent insert)</td>
<td>Not support</td>
<td>Not support</td>
<td>Not support</td>
</tr>
</tbody>
</table>
<h5 id="block-cache">Block Cache</h5>
<ul>
<li><strong>Block cache</strong> is where RocksDB caches data in memory for reads. User can pass in a Cache object to a RocksDB instance with a desired capacity (size). A Cache object can be shared by multiple RocksDB instances in the same process, allowing users to control the overall cache capacity. The block cache stores uncompressed blocks. Optionally user can set a second block cache storing compressed blocks. Reads will fetch data blocks first from uncompressed block cache, then compressed block cache. The compressed block cache can be a replacement of OS page cache, if Direct-IO is used.</li>
<li>There are two cache implementations in RocksDB, namely <code>LRUCache</code> and <code>ClockCache</code>. Both types of the cache are sharded to mitigate lock contention. Capacity is divided evenly to each shard and shards don't share capacity. By default each cache will be sharded into at most 64 shards, with each shard has no less than 512k bytes of capacity.</li>
<li><strong>In default, RocksDB will use LRU-based block cache implementation with 8MB capacity</strong>.</li>
<li><code>LRUCache</code> vs <code>ClockCache</code> in RocksDB: https://github.com/facebook/rocksdb/wiki/Block-Cache#clock-cache</li>
<li>If the data block is not found in block cache, RocksDB reads it from file using buffered IO. That means it also uses the OS's page cache for raw file blocks, usually containing compressed data. In a way, RocksDB's cache is two-tiered: block cache and page cache. Counter-intuitively, decreasing block cache size will not increase IO. The memory saved will likely be used for page cache, so even more data will be cached. However, CPU usage might grow because RocksDB needs to decompress pages it reads from page cache.</li>
</ul>
<h5 id="indexes-and-filter-blocks">Indexes and filter blocks</h5>
<ul>
<li><strong>Indexes and filter blocks</strong> can be big memory users and by default they don't count in memory you allocate for block cache. This can sometimes cause confusion for users: you allocate 10GB for block cache, but RocksDB is using 15GB of memory. The difference is usually explained by index and bloom filter blocks.</li>
<li>If you set <code>cache_index_and_filter_blocks</code> to <code>true</code>, index and filter blocks will be stored in block cache, together with all other data blocks.</li>
</ul>
<h5 id="blocks-pinned-by-iterators">Blocks pinned by iterators</h5>
<ul>
<li>Blocks pinned by iterators usually don't contribute much to the overall memory usage. However, in some cases, when you have 100k read transactions happening simultaneously, it might put a strain on memory. Memory usage for pinned blocks is easy to calculate. Each iterator pins exactly one data block for each L0 file plus one data block for each L1+ level.</li>
</ul>
<h5 id="sst-file-index">SST File Index</h5>
<ul>
<li><a href="https://github.com/facebook/rocksdb/wiki/Indexing-SST-Files-for-Better-Lookup-Performance">Indexing SST Files for Better Lookup Performance</a></li>
</ul>
<h5 id="wal">WAL</h5>
<ul>
<li><strong>Write Ahead Log</strong>: Every update to RocksDB is written to two places: 1) an in-memory data structure called memtable (to be flushed to SST files later) and 2) write ahead log(WAL) on disk. In the event of a failure, write ahead logs can be used to completely recover the data in the memtable, which is necessary to restore the database to the original state. In the default configuration, RocksDB guarantees process crash consistency by <strong>flushing the WAL after every user write</strong>.</li>
<li>A WAL is created when 1) a new DB is opened, 2) a column family is flushed. A WAL is deleted (or archived if archival is enabled) when all column families have flushed beyond the largest sequence number contained in the WAL, or in other words, all data in the WAL have been persisted to SST files. Archived WALs will be moved to a separate location and purged from disk later on. The actual deletion might be delayed due to replication purposes</li>
<li><strong>Write ahead log (WAL)</strong> serializes memtable operations to persistent medium as log files. In the event of a failure, WAL files can be used to recover the database to its consistent state, by reconstructing the memtable from the logs. When a memtable is flushed out to persistent medium safely, the corresponding WAL log(s) become obsolete and are archived. Eventually the archived logs are purged from disk after a certain period of time. https://github.com/facebook/rocksdb/wiki/Write-Ahead-Log</li>
<li><strong>Log File Format</strong>：Log file consists of a sequence of variable length records. Records are grouped by <code>kBlockSize</code>(32k). If a certain record cannot fit into the leftover space, then the leftover space is padded with empty (null) data. The writer writes and the reader reads in chunks of <code>kBlockSize</code>. https://github.com/facebook/rocksdb/wiki/Write-Ahead-Log-File-Format</li>
</ul>
<pre><code>       +-----+-------------+--+----+----------+------+-- ... ----+
 File  | r0  |        r1   |P | r2 |    r3    |  r4  |           |
       +-----+-------------+--+----+----------+------+-- ... ----+
       &lt;--- kBlockSize ------&gt;|&lt;-- kBlockSize ------&gt;|

  rn = variable size records
  P = Padding
</code></pre>
<ul>
<li><strong>Record Format</strong>：The record layout format is as shown below. There are two kinds of record format, Legacy and Recyclable:
<ul>
<li><strong>The Legacy Record Format</strong>：</li>
</ul>
</li>
</ul>
<pre><code>+---------+-----------+-----------+--- ... ---+
|CRC (4B) | Size (2B) | Type (1B) | Payload   |
+---------+-----------+-----------+--- ... ---+

CRC = 32bit hash computed over the payload using CRC
Size = Length of the payload data
Type = Type of record
       (kZeroType, kFullType, kFirstType, kLastType, kMiddleType )
       The type is used to group a bunch of records together to represent
       blocks that are larger than kBlockSize
Payload = Byte stream as long as specified by the payload size
</code></pre>
<ul>
<li><strong>The Recyclable Record Format</strong></li>
</ul>
<pre><code>+---------+-----------+-----------+----------------+--- ... ---+
|CRC (4B) | Size (2B) | Type (1B) | Log number (4B)| Payload   |
+---------+-----------+-----------+----------------+--- ... ---+
Same as above, with the addition of
Log number = 32bit log file number, so that we can distinguish between
records written by the most recent log writer vs a previous one.
</code></pre>
<ul>
<li>
<p><strong>WAL Perfoemance # Write Amplification</strong>: Note that for some use cases, synchronous WAL can introduce non-trivial write amplification. When writes are small, because complete block/page might need to be updated, we may end up with two 4KB writes (one for data and one for metadata) even if the write is very small. If write is only 40 bytes, 8KB is updated, the write amplification is 8 KB/40 bytes ~= 200. It can easily be even larger than the write amplification by LSM-tree.</p>
</li>
<li>
<p><strong>SST</strong>: Sorted String Table.</p>
<ul>
<li><strong>BlockBasedTable</strong> is the default SST table format in RocksDB. https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format</li>
</ul>
<pre><code>  &lt;beginning_of_file&gt;
  [data block 1]
  [data block 2]
  ...
  [data block N]
  [meta block 1: filter block]                  (see section: &quot;filter&quot; Meta Block)
  [meta block 2: index block]
  [meta block 3: compression dictionary block]  (see section: &quot;compression dictionary&quot; Meta Block)
  [meta block 4: range deletion block]          (see section: &quot;range deletion&quot; Meta Block)
  [meta block 5: stats block]                   (see section: &quot;properties&quot; Meta Block)
  ...
  [meta block K: future extended block]  (we may add more meta blocks in the future)
  [metaindex block]
  [Footer]                               (fixed size; starts at file_size - sizeof(Footer))
  &lt;end_of_file&gt;
</code></pre>
<ul>
<li><strong>PlainTable Format</strong>: PlainTable is a RocksDB's SST file format optimized for low query latency on pure-memory or really low-latency media. https://github.com/facebook/rocksdb/wiki/PlainTable-Format</li>
<li><strong>CuckooTable Format</strong>: We introduce a new SST file format based on Cuckoo Hashing which is optimized for very high point lookup rates. Applications which don't use range scan but require very fast point lookups can use this new table format. https://github.com/facebook/rocksdb/wiki/CuckooTable-Format</li>
<li><strong>Index Block Format</strong>: An index block contains one entry per data block, where the key is a string &gt;= last key in that data block and before the first key in the successive data block. The value is the BlockHandle (file offset and length) for the data block. https://github.com/facebook/rocksdb/wiki/Index-Block-Format</li>
<li><strong>Bloom Filter</strong>: In RocksDB, when the filter policy is set, every newly created SST file will contain a Bloom filter, which is used to determine if the file may contain the key we're looking for. The filter is essentially a bit array. Multiple hash functions are applied to the given key, each specifying a bit in the array that will be set to 1. At read time also the same hash functions are applied on the search key, the bits are checked, i.e., probe, and the key definitely does not exist if at least one of the probes return 0. https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter</li>
<li><strong>Data Block Hash Index</strong>: RocksDB does a binary search when performing point lookup the keys in data blocks. However, in order to find the right location where the key may reside, multiple key parsing and comparison are needed. Each binary search branching triggers CPU cache miss, causing much CPU utilization. We have seen that this binary search takes up considerable CPU in production use-cases. A hash index is designed and implemented in RocksDB data blocks to improve the CPU efficiency of point lookup. Benchmarks with db_bench show the CPU utilization of one of the main functions in the point lookup code path, DataBlockIter::Seek(), is reduced by 21.8%, and the overall RocksDB throughput is increased by 10% under purely cached workloads, at an overhead of 4.6% more space. https://github.com/facebook/rocksdb/wiki/Data-Block-Hash-Index</li>
</ul>
</li>
<li>
<p><strong>MANIFEST</strong>: MANIFEST refers to the system that keeps track of RocksDB state changes in a transactional log. RocksDB has a built-in mechanism to overcome these limitations of POSIX file system by keeping a transactional log of RocksDB state changes using Version Edit Records in the Manifest log files. MANIFEST is used to restore RocksDB to the latest known consistent state on a restart. https://github.com/facebook/rocksdb/wiki/MANIFEST</p>
</li>
</ul>
<h4 id="main-operations">Main Operations</h4>
<ul>
<li>Get</li>
<li>Put</li>
<li>Delete</li>
<li>NewIterator</li>
</ul>
<h4 id="readwrite-processes">Read/Write Processes</h4>
<h5 id="read">Read</h5>
<figure data-type="image" tabindex="2"><img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210102164947.png" alt="20210102164947" loading="lazy"></figure>
<ul>
<li>Mutable Memtable -&gt; Immutable Memtable -&gt; All SSTable files in L0 -&gt; Some SSTable files in Ln.</li>
<li>For memtables and SSTables files, look up bloom filter firstly to determine if the file may contain the key. If contains, search this file and look up.</li>
<li>For file internal search operation
<ul>
<li>Memtable: Use Skiplist to find the value.</li>
<li>SSTable files: Use Hash Index and Binary Search Index to find the data block. Load the data block to memory and search the value.</li>
</ul>
</li>
<li>For SSTable files search, use SST File Index to determine which files contains the given key and only search these files.</li>
</ul>
<pre><code>
                                         file 1                                          file 2
                                      +----------+                                    +----------+
level 1:                              | 100, 200 |                                    | 300, 400 |
                                      +----------+                                    +----------+
           file 1     file 2      file 3      file 4       file 5       file 6       file 7       file 8
         +--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+
level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 | | 410, 450 |
         +--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+

</code></pre>
<h5 id="write">Write</h5>
<ul>
<li>WAL -&gt; Mutable Memtable -&gt; Immutable Memtable -&gt; SSTable in L0 (unordered in different SST file but ordered in the file) -&gt; SSTable in Ln</li>
</ul>
<h3 id="core-concepts">Core Concepts</h3>
<h4 id="compaction">Compaction</h4>
<ul>
<li>https://github.com/facebook/rocksdb/wiki/Compaction</li>
<li><a href="https://smalldatum.blogspot.com/2018/08/name-that-compaction-algorithm.html">Name that compaction algorithm</a></li>
<li>Here we present a taxonomy of compaction algorithms: Classic Leveled, Tiered, Tiered+Leveled, Leveled-N, FIFO. Out of them, Rocksdb implements Tiered+Leveled, termed Level Compaction in the code, Tiered termed Universal in the code, and FIFO.</li>
<li><strong>Some concepts you must learn</strong>:
<ul>
<li>read/write/space amplification
<ul>
<li>read amplification</li>
<li>write amplification</li>
<li>space amplification</li>
</ul>
</li>
<li>Run: The on-disk data is organized into sorted runs of data. Each run contains data <strong>sorted</strong> by the index key. A run can be represented on disk as a single file, or alternatively as a collection of files with <strong>non-overlapping key ranges</strong>.</li>
</ul>
</li>
</ul>
<h5 id="leveled">Leveled</h5>
<ul>
<li><strong>Leveled compaction minimizes space amplification at the cost of read and write amplification.</strong>
<ul>
<li>https://rocksdb.org.cn/doc/Leveled-Compaction.html</li>
<li>https://github.com/facebook/rocksdb/wiki/Leveled-Compaction</li>
<li>https://www.scylladb.com/2018/01/31/compaction-series-leveled-compaction/</li>
<li>While write amplification is usually worse with leveled than with tiered, there are a few cases where leveled is competitive. The first is key-order inserts and a RocksDB optimization greatly reduces write-amp in that case. The second one is skewed writes where only a small fraction of the keys are likely to be updated. With the right value for compaction priority in RocksDB compaction should stop at the smallest level that is large enough to capture the write working set -- it won't go all the way to the max level. When leveled compaction is some-to-some then compaction is only done for the slices of the LSM tree that overlap the written keys, which can generate less write amplification than all-to-all compaction.<br>
<img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210103155949.png" alt="20210103155949" loading="lazy"></li>
<li>When the amount of files in L0 exceeds <code>level0_file_num_compaction_trigger</code>, compactions will be triggered and must choose <strong>all files in L0</strong> because of unordered data for different files.<br>
<img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210103160027.png" alt="20210103160027" loading="lazy"></li>
<li>After merging to L1, the size of L1 may exceed the target size and need to execute new compactions. For L1, choose at least 1 file and merge with overlapped key range files in L2.<br>
<img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210103160042.png" alt="20210103160042" loading="lazy"></li>
<li>If necessary, multiple compaction operations can be executed concurrently with the control of param <code>max_background_compactions</code>.<br>
<img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210103160142.png" alt="20210103160142" loading="lazy"></li>
<li>However for L0-&gt;L1 compaction operation, it can not be executed concurrently. And it may become bottlenech for compaction speed, <code>max_subcompactions</code> can be used to partion the data in L0 and execute compactions with multi threads.<br>
<img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210103161012.png" alt="20210103161012" loading="lazy"></li>
</ul>
</li>
<li><strong>The job of Leveled compaction strategy is to maintain this structure while keeping L0 empty</strong>
<ul>
<li>When we have enough (e.g., 4) sstables in L0, we compact them into L1 by <strong>compacting all the sstables in L0 together with all the sstables in L1</strong>.</li>
<li>The new run in L1 may have more than the desired 10 sstables. If that happens, we pick one sstable from L1 and compact it into L2</li>
<li>After we compacted a table from L1 into L2, now L2 may have more than the desired number of sstables, so we compact sstables from L2 into L3. Again, this involves compacting one sstable from L2 and about 10 sstables from L3<br>
<img src="https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210108104335.png" alt="20210108104335" loading="lazy"></li>
</ul>
</li>
</ul>
<h5 id="leveled-n">Leveled-N</h5>
<ul>
<li><strong>Leveled-N compaction is like leveled compaction but with less write and more read amplification.</strong> It allows <strong>more than one sorted run per level</strong>. Compaction merges all sorted runs from Ln-1 into one sorted run from Ln, which is leveled. And then &quot;-N&quot; is added to the name to indicate there can be n sorted runs per level. The Dostoevsky paper defined a compaction algorithm named Fluid LSM in which the max level has 1 sorted run but the non-max levels can have more than 1 sorted run. Leveled compaction is done into the max level.</li>
</ul>
<h5 id="tiered">Tiered</h5>
<ul>
<li><strong>Tiered compaction minimizes write amplification at the cost of read and space amplification.</strong></li>
</ul>
<h2 id="write-amplification-in-rocksdb">Write Amplification in RocksDB</h2>
<h1 id="solutions">Solutions</h1>
<h2 id="industry">Industry</h2>
<h3 id="case-one-pingcap-titan">CASE ONE: PingCAP - Titan</h3>
<h3 id="case-two-toshiba-toshibamemory">CASE TWO: Toshiba - ToshibaMemory</h3>
<h3 id="case-three-bytedance">CASE THREE: ByteDance</h3>
<h2 id="academia">Academia</h2>
<h2 id="references-2">References</h2>
<ul>
<li><a href="https://en.pingcap.com/blog/titan-storage-engine-design-and-implementation">[1] PingCAP - Titan</a></li>
<li><a href="https://www.snia.org/sites/default/files/SDC/2019/presentations/NVMe/Brasga_Remington_Enhancing_RocksDB_for_SSD_Endurance_and_Performance.pdf">[2] ToshibaMemory - Toshiba</a></li>
<li><a href="https://www.infoq.cn/article/u3leu3emgjjwflqltjhs">[3] InfoQ - ByteDance Practice</a></li>
<li><a href="https://xie.infoq.cn/article/279e0ad88fe7b0e293adce7fb">[4] InfoQ - TiDB 原理解析</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/141186118">[5] 知乎 - 叶提：深入探讨LSM Compaction机制</a></li>
<li><a href="https://www.jianshu.com/p/e89cd503c9ae">[6] 简书 - LittleMagic：LSM Tree-Based存储引擎的compaction策略（feat. RocksDB）</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/112574579">[7] 知乎 - 张睿：LSM Tree的Leveling 和 Tiering Compaction</a></li>
<li><a href="https://scholar.harvard.edu/files/stratos/files/dostoevskykv.pdf">[8] Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging</a></li>
</ul>

                </div>
                <div class="clear"></div>
              </section>
            </article>
            <div class="clear"></div>

            <section class="related section">
              
              <article class="prev grid-50 tablet-grid-50 grid-parent">
                <div class="thumb cover lazy loaded" style="background-image: url('https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20201210191906.png');"></div>
                 <a href="https://blog.shunzi.tech/post/Alluxio/" class="full-link"></a>
                 <div class="info">
                  <time datetime="2020-12-10">2020-12-10</time>
                  <h4 class="title white no-margin">Alluxio</h4>
                </div>
                 <span class="epcl-button red">
                  <img src="https://blog.shunzi.tech/media/images/left-arrow.svg" width="15" alt="Left Arrow">
                </span>
                <div class="overlay"></div>
              </article>
              
              
              <article class="next grid-50 tablet-grid-50 grid-parent">
                <div class="thumb cover lazy loaded" style="background-image: url('https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20201107165512.png');"></div>
                 <a href="https://blog.shunzi.tech/post/osdi-Bourbon/" class="full-link"></a>
                 <div class="info">
                  <time datetime="2020-11-06">2020-11-06</time>
                  <h4 class="title white no-margin">From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees</h4>
                </div>
                 <span class="epcl-button red">
                  <img src="https://blog.shunzi.tech/media/images/right-arrow.svg" width="15" alt="Left Arrow">
                </span>
                <div class="overlay"></div>
              </article>
              

                <div class="clear"></div>
            </section>

              <div class="clear"></div>
              
            
              <div id="comments" class="bg-white hosted ">
                <div class="clear"></div>
<script>
jQuery(document).ready(function($){
    $('.vemoji-btn').text('😀');
    $("#comments").on('click', 'span.vat',function(){
        $(this).parent('div.vmeta').next("div.vcontent").after($("div.vwrap"));
        $('textarea#veditor').focus();
    })
    if(window.location.hash){
        var checkExist = setInterval(function() {
            if ($(window.location.hash).length) {
                $('html, body').animate({scrollTop: $(window.location.hash).offset().top-200}, 600);
                clearInterval(checkExist);
            }
        }, 100);
    }
})
</script>

              </div>
            

            </div>
          </div>
      </main>

          <footer id="footer" class="grid-container">
        <div class="widgets row gradient-effect">
            <div class="default-sidebar border-effect">
              <div class="grid-33 tablet-grid-50 mobile-grid-100">
                <section id="tag_cloud-2" class="widget widget_epcl_posts_thumbs underline-effect">
                  <h4 class="widget-title title white bordered">最新文章</h4>
                  
                  
                  <article class="item post-0 post type-post status-publish format-standard has-post-thumbnail hentry">
                    <a href="https://blog.shunzi.tech/post/Dostoevsky/" class="thumb hover-effect">
                      <span class="fullimage cover" style="display:block;border-radius:50%;background-image: url('https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20210112173749.png)');"></span>
                    </a>
                    <div class="info gradient-effect">
                      <time datetime="2021-01-12">2021-01-12</time>
                      <h4 class="title usmall">
                        <a href="https://blog.shunzi.tech/post/Dostoevsky/">Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging</a>
                      </h4>
                    </div>
                    <div class="clear"></div>
                  </article>
                  
                  
                  
                  <article class="item post-1 post type-post status-publish format-standard has-post-thumbnail hentry">
                    <a href="https://blog.shunzi.tech/post/CRaft/" class="thumb hover-effect">
                      <span class="fullimage cover" style="display:block;border-radius:50%;background-image: url('https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20200614213040.png');"></span>
                    </a>
                    <div class="info gradient-effect">
                      <time datetime="2020-12-16">2020-12-16</time>
                      <h4 class="title usmall">
                        <a href="https://blog.shunzi.tech/post/CRaft/">CRaft: An Erasure-coding-supported Version of Raft for Reducing Storage Cost and Network Cost</a>
                      </h4>
                    </div>
                    <div class="clear"></div>
                  </article>
                  
                  
                  
                  <article class="item post-2 post type-post status-publish format-standard has-post-thumbnail hentry">
                    <a href="https://blog.shunzi.tech/post/Alluxio/" class="thumb hover-effect">
                      <span class="fullimage cover" style="display:block;border-radius:50%;background-image: url('https://raw.githubusercontent.com/zjs1224522500/PicGoImages/master//img/blog/20201210191906.png');"></span>
                    </a>
                    <div class="info gradient-effect">
                      <time datetime="2020-12-10">2020-12-10</time>
                      <h4 class="title usmall">
                        <a href="https://blog.shunzi.tech/post/Alluxio/">Alluxio</a>
                      </h4>
                    </div>
                    <div class="clear"></div>
                  </article>
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  <div class="clear"></div>
                </section>
              </div>

              <div class="grid-33 tablet-grid-50 mobile-grid-100">
                <section id="tag_cloud-2" class="widget widget_tag_cloud underline-effect">
                  <h4 class="widget-title title white bordered">标签云</h4>
                  <div class="tagcloud">
                    
                      <a href="https://blog.shunzi.tech/tag/l8sKsLUAi/" class="ctag ctag-0 ctag-l8sKsLUAi" aria-label="">KVS</a>
                    
                      <a href="https://blog.shunzi.tech/tag/5uQUdLlSC/" class="ctag ctag-1 ctag-5uQUdLlSC" aria-label="">Paper</a>
                    
                      <a href="https://blog.shunzi.tech/tag/3zCwFWPHxH/" class="ctag ctag-2 ctag-3zCwFWPHxH" aria-label="">存储</a>
                    
                      <a href="https://blog.shunzi.tech/tag/geK0jEW-T/" class="ctag ctag-3 ctag-geK0jEW-T" aria-label="">分布式</a>
                    
                      <a href="https://blog.shunzi.tech/tag/9msH-lUaA/" class="ctag ctag-4 ctag-9msH-lUaA" aria-label="">缓存</a>
                    
                      <a href="https://blog.shunzi.tech/tag/_jfuTNqah/" class="ctag ctag-5 ctag-_jfuTNqah" aria-label="">LSM</a>
                    
                      <a href="https://blog.shunzi.tech/tag/i2b42Y2j6/" class="ctag ctag-6 ctag-i2b42Y2j6" aria-label="">Ceph</a>
                    
                      <a href="https://blog.shunzi.tech/tag/la-n8a0mo/" class="ctag ctag-7 ctag-la-n8a0mo" aria-label="">读书笔记</a>
                    
                      <a href="https://blog.shunzi.tech/tag/os/" class="ctag ctag-8 ctag-os" aria-label="">OS</a>
                    
                      <a href="https://blog.shunzi.tech/tag/oBVOD8v4ou/" class="ctag ctag-9 ctag-oBVOD8v4ou" aria-label="">一致性</a>
                    
                      <a href="https://blog.shunzi.tech/tag/gqgftpk_y/" class="ctag ctag-10 ctag-gqgftpk_y" aria-label="">AI</a>
                    
                      <a href="https://blog.shunzi.tech/tag/shu-ju-ku/" class="ctag ctag-11 ctag-shu-ju-ku" aria-label="">数据库</a>
                    
                      <a href="https://blog.shunzi.tech/tag/n2w6bz87h/" class="ctag ctag-12 ctag-n2w6bz87h" aria-label="">编程语言</a>
                    
                      <a href="https://blog.shunzi.tech/tag/ZnIN9Ge-w/" class="ctag ctag-13 ctag-ZnIN9Ge-w" aria-label="">对象存储</a>
                    
                      <a href="https://blog.shunzi.tech/tag/4zx4ysLGro/" class="ctag ctag-14 ctag-4zx4ysLGro" aria-label="">云计算</a>
                    
                      <a href="https://blog.shunzi.tech/tag/NgjQJdkc6/" class="ctag ctag-15 ctag-NgjQJdkc6" aria-label="">项目</a>
                    
                      <a href="https://blog.shunzi.tech/tag/5h7k39FKw/" class="ctag ctag-16 ctag-5h7k39FKw" aria-label="">C语言</a>
                    
                      <a href="https://blog.shunzi.tech/tag/c0aMcnBDAh/" class="ctag ctag-17 ctag-c0aMcnBDAh" aria-label="">C++</a>
                    
                      <a href="https://blog.shunzi.tech/tag/NF-h45xcE/" class="ctag ctag-18 ctag-NF-h45xcE" aria-label="">iscsi</a>
                    
                      <a href="https://blog.shunzi.tech/tag/Y_nsOD1At/" class="ctag ctag-19 ctag-Y_nsOD1At" aria-label="">SSD</a>
                    
                      <a href="https://blog.shunzi.tech/tag/E2d1yYZcV8/" class="ctag ctag-20 ctag-E2d1yYZcV8" aria-label="">虚拟化</a>
                    
                      <a href="https://blog.shunzi.tech/tag/PhD/" class="ctag ctag-21 ctag-PhD" aria-label="">Ph.D</a>
                    
                      <a href="https://blog.shunzi.tech/tag/ZqEqvRTvl/" class="ctag ctag-22 ctag-ZqEqvRTvl" aria-label="">网络</a>
                    
                      <a href="https://blog.shunzi.tech/tag/PuY19cs53/" class="ctag ctag-23 ctag-PuY19cs53" aria-label="">仿真</a>
                    
                      <a href="https://blog.shunzi.tech/tag/rIIc9E-ZvN/" class="ctag ctag-24 ctag-rIIc9E-ZvN" aria-label="">系统结构</a>
                    
                      <a href="https://blog.shunzi.tech/tag/fu-wu-qi/" class="ctag ctag-25 ctag-fu-wu-qi" aria-label="">服务器</a>
                    
                      <a href="https://blog.shunzi.tech/tag/X-lnqf1Ex/" class="ctag ctag-26 ctag-X-lnqf1Ex" aria-label="">容器</a>
                    
                      <a href="https://blog.shunzi.tech/tag/hbaTDSglx-/" class="ctag ctag-27 ctag-hbaTDSglx-" aria-label="">工具</a>
                    
                      <a href="https://blog.shunzi.tech/tag/EO3XpMf_y/" class="ctag ctag-28 ctag-EO3XpMf_y" aria-label="">Linux</a>
                    
                      <a href="https://blog.shunzi.tech/tag/diary/" class="ctag ctag-29 ctag-diary" aria-label="">Diary</a>
                    
                      <a href="https://blog.shunzi.tech/tag/DyzFtOe6x/" class="ctag ctag-30 ctag-DyzFtOe6x" aria-label="">计算机基础</a>
                    
                      <a href="https://blog.shunzi.tech/tag/oqE3oKihb/" class="ctag ctag-31 ctag-oqE3oKihb" aria-label="">OpenStack</a>
                    
                      <a href="https://blog.shunzi.tech/tag/p_z7gKe6R/" class="ctag ctag-32 ctag-p_z7gKe6R" aria-label="">中间件</a>
                    
                      <a href="https://blog.shunzi.tech/tag/Test/" class="ctag ctag-33 ctag-Test" aria-label="">测试</a>
                    
                      <a href="https://blog.shunzi.tech/tag/Product-Standard/" class="ctag ctag-34 ctag-Product-Standard" aria-label="">Product Standard</a>
                    
                      <a href="https://blog.shunzi.tech/tag/spring/" class="ctag ctag-35 ctag-spring" aria-label="">Spring</a>
                    
                      <a href="https://blog.shunzi.tech/tag/she-ji-mo-shi/" class="ctag ctag-36 ctag-she-ji-mo-shi" aria-label="">设计模式</a>
                    
                      <a href="https://blog.shunzi.tech/tag/mian-jing/" class="ctag ctag-37 ctag-mian-jing" aria-label="">面经</a>
                    
                      <a href="https://blog.shunzi.tech/tag/suan-fa/" class="ctag ctag-38 ctag-suan-fa" aria-label="">算法</a>
                    
                      <a href="https://blog.shunzi.tech/tag/redis/" class="ctag ctag-39 ctag-redis" aria-label="">Redis</a>
                    
                      <a href="https://blog.shunzi.tech/tag/javaweb/" class="ctag ctag-40 ctag-javaweb" aria-label="">JavaWeb</a>
                    
                      <a href="https://blog.shunzi.tech/tag/KyMCZj2Wl/" class="ctag ctag-41 ctag-KyMCZj2Wl" aria-label="">WEB容器</a>
                    
                      <a href="https://blog.shunzi.tech/tag/javase/" class="ctag ctag-42 ctag-javase" aria-label="">JavaSE</a>
                    
                  </div>
                  <div class="clear"></div>
                </section>
              </div>

              <div class="grid-33 tablet-grid-50 mobile-grid-100">
                <section id="epcl_about-2" class="widget widget_epcl_about underline-effect">
                  <h4 class="widget-title title white bordered">关于我</h4>
                  <div class="avatar">
                    <a href="" class="translate-effect thumb"><span class="fullimage cover" style="background-image: url(https://blog.shunzi.tech/images/avatar.png);"></span></a>
                  </div>
                  <div class="info">
                    <h4 class="title small author-name gradient-effect no-margin"><a href="">Elvis Zhang</a></h4>
                    <p class="founder">The easy way or the right way.</p>
                    <div class="social">
                      
                          
                            <a href="https://github.com/zjs1224522500" class="translate-effect" target="_blank"><i class="fa fa-github"></i></a>
                        
                      
                          
                            <a href="https://twitter.com/1224522500Elvis" class="translate-effect" target="_blank"><i class="fa fa-twitter"></i></a>
                        
                      
                        
                      
                        
                      
                        
                      
                    </div> 
                  </div>
                  <div class="clear"></div>
                  </section>
              </div>

            </div>
            <div class="clear"></div>
        </div>

        <div class="logo">
          <a href="https://blog.shunzi.tech"><img src="\media\images\custom-footerLogo.jpg" alt=""></a>
        </div>
        <p class="published border-effect">
          ©2019 共 107 篇文章
          <br/>
          Theme <a href="https://gridea.dev/" target="_blank">「breek」</a> Powered by <a href="https://gridea.dev/" target="_blank">「Gridea」</a>
        </p>
        
        <a href="javascript:void(0)" id="back-to-top" class="epcl-button dark" style="display:none">
          <i class="fa fa-arrow"></i>
        </a>
    </footer>
    
    <div class="clear"></div>

        
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/leancloud-storage/dist/av-min.js"></script>
<script type="text/javascript" src="https://cdn.staticfile.org/valine/1.3.10/Valine.Pure.min.js"></script>
<script>
    new Valine({
        el: '#comments',
        appId: 'Pj5H1z0w7hJlLGJpGBh9NrCq-MdYXbMMI' ,
        appKey: 'LdR8vK5EaBfK87esF7tlbsXe',
        pageSize: 30,
        placeholder: '既然来了，那就留个痕迹吧~',
        visitor: true // 阅读量统计
    })
</script>
    

      
    <script src="https://blog.shunzi.tech/media/js/functions-post.js"></script>

    </div>
    <!-- end: #wrapper -->
  </body>
</html>
